package mine.code.question.动态规划;

import org.junit.Test;

/**
 * 给你一个正整数数组 values，其中 values[i]表示第 i 个观光景点的评分，并且两个景点i 和j之间的 距离 为j - i。
 * <p>
 * 一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
 * <p>
 * 返回一对观光景点能取得的最高分。
 * <p>
 * 示例 1：
 * <p>
 * 输入：values = [8,1,5,2,6]
 * 输出：11
 * 解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
 *
 * @author caijinnan
 */
public class 最佳观光组合 {

    @Test
    public void run() {
        int[] values = {101, 2, 3, 4, 100, 1, 100};
        System.out.println(maxScoreSightseeingPair(values));
    }

    public int maxScoreSightseeingPair(int[] values) {
        // dp[i] = max(dp[i-1],max(values[i]))
        int[] dp = new int[values.length];
        dp[0] = 0;
        int maxIndex = 0;
        for (int i = 1; i < values.length; i++) {
            int max = values[i] + values[maxIndex] + maxIndex - i;
            dp[i] = Math.max(dp[i - 1], max);
            if (values[i] > values[maxIndex] + maxIndex - i) {
                maxIndex = i;
            }
        }
        return dp[values.length - 1];
    }
}
